//-----------------------------------------------------------
//  Purpose:    Compare two recursive power functions.
//  Author:     John Gauch
//-----------------------------------------------------------

#include <iostream>
using namespace std;

int calls;

//-----------------------------------------------------------
// This function will take log(P)+1 recursive calls to calculate X^P
//-----------------------------------------------------------
float power(float x, int p)
{
   calls++;
   
   // Check terminating conditions
   if (p == 0)
      return 1;
   else if (p == 1)
      return x;

   // Handle recursive cases
   else if (p < 0)
      return 1.0 / power(x, -p);

   else if (p % 2 == 0)  
   {
      float temp = power(x, p / 2);       // A
      return temp * temp;
   }
   else if (p % 2 == 1) 
   {
      float temp = power(x, p / 2);       // B
      return x * temp * temp;
   }
   else
      return 0.0;
}

//-----------------------------------------------------------
// This function will take 2P-1 recursive calls to calculate X^P
//-----------------------------------------------------------
float power2(float x, int p)
{
   calls++;
   
   // Check terminating conditions
   if (p == 0)
      return 1;
   else if (p == 1)
      return x;

   // Handle recursive cases
   else if (p < 0)
      return 1.0 / power2(x, -p);

   else if (p % 2 == 0)  
   {
      return power2(x, p/2) * power2(x, p/2);       // A
   }
   else if (p % 2 == 1) 
   {
      return power2(x,1+p/2) * power2(x, p/2);      // B
   }
   else
      return 0.0;
}

//-----------------------------------------------------------
// Main program
//-----------------------------------------------------------
int main()
{
   float x = 0;
   cout << "enter x: ";
   cin >> x;

   int p = 0;
   cout << "enter p: ";
   cin >> p;

   calls = 0;
   cout << "answer: " << power(x, p) << endl;
   cout << "calls: " << calls << endl;

   calls = 0;
   cout << "answer: " << power2(x, p) << endl;
   cout << "calls: " << calls << endl;
}